#pragma once
#include <list>
using namespace std;
/// <summary>
/// A SortedTree is like a SortedList, but a node can have multiple items that are all equal.
/// </summary>
/// <typeparam name="T"></typeparam>
template <typename T> class SortedTree
{
public:
	/// <summary>
	/// List of items in this node.
	/// </summary>
	list<T*>Items;
	/// <summary>
	/// Nodes that are less than this node.
	/// </summary>
	SortedTree<T>* LessThan;
	/// <summary>
	/// Nodes that are greater than this node. 
	/// </summary>
	SortedTree<T>* GreaterThan;
	/// <summary>
	/// Should SortedTree delete the item when finished. Don't delete integers for instance.
	/// </summary>
	bool CanDeleteItem;
	/// <summary>
	/// Constructor.
	/// </summary>
	/// <param name="canDeleteItem">Should SortedTree delete the item when finished</param>
	SortedTree(bool canDeleteItem)
	{
		LessThan = NULL;
		GreaterThan = NULL;
		CanDeleteItem = canDeleteItem;
	}
	/// <summary>
	/// Delete Items and delete all the child nodes.
	/// </summary>
	void Clear()
	{
		SortedTree<T>* loop;
		list<SortedTree<T>*> items;
		T* item;
		// It's easy to code a recurive delete. But recursive delete can sometimes crash the stack if the tree is big.
		if (LessThan != NULL)
		{
			items.push_back(LessThan);
			LessThan = NULL;
		}
		if (GreaterThan != NULL)
		{
			items.push_back(GreaterThan);
			GreaterThan = NULL;
		}
		while (!items.empty())
		{
			loop = items.front();
			items.pop_front();
			if (loop->LessThan != NULL)
			{
				items.push_back(loop->LessThan);
				loop->LessThan = NULL;
			}
			if (loop->GreaterThan != NULL)
			{
				items.push_back(loop->GreaterThan);
				loop->GreaterThan = NULL;
			}
			delete loop;
		}
		if (CanDeleteItem)
		{
			while (!Items.empty())
			{
				item = Items.front();
				Items.pop_front();
				delete item;
			}
		}
		else
		{
			Items.clear();
		}		
	}
	/// <summary>
	/// Destructor.
	/// </summary>
	~SortedTree()
	{
		Clear();
	}
	/// <summary>
	/// Search for an item. 
	/// </summary>
	/// <param name="item">Item to search for</param>
	/// <param name="compareFunction">Function to use to compare the items</param>
	/// <returns>Returns the node of the found item or NULL if not found.</returns>
	SortedTree<T>* FindItem(T* item, int (compareFunction)(const T* item1, const T* item2))
	{
		SortedTree<T>* loop = this;
		int compare;
		while (loop != NULL)
		{
			compare = compareFunction(item, loop->Items.front());
			if (compare == 0)
			{
				break;
			}
			if (compare < 0)
			{
				loop = loop->LessThan;
			}
			else
			{
				loop = loop->GreaterThan;
			}
		}
		return loop;
	}

	/// <summary>
	/// Adds a item to the tree.
	/// </summary>
	/// <param name="item">Item to add</param>
	/// <param name="compareFunction">Compare function to compare two items.</param>
	void AddItem(T* item, int (compareFunction)(const T* item1, const T* item2))
	{
		SortedTree<T>* loop = this;
		SortedTree<T>* next;
		int compare;
		while (true)
		{
			compare = compareFunction(item, loop->Items.front());
			if (compare == 0)
			{
				loop->Items.push_back(item);
				break;
			}
			if (compare < 0)
			{
				next = loop->LessThan;
				if (next == NULL)
				{
					next = new SortedTree<T>(CanDeleteItem);
					next->Items.push_back(item);
					loop->LessThan = next;
					break;
				}				
			}
			else
			{
				next = loop->GreaterThan;
				if (next == NULL)
				{
					next = new SortedTree<T>(CanDeleteItem);
					next->Items.push_back(item);
					loop->GreaterThan = next;
					break;
				}
			}
			loop = next;
		}		
	}
};

